package net.tp.algo.text;

import java.util.*;

/**
 *
 * <p>Rules for building NFA:</p>
 * <ul>
 *     <li>Add nodes for each character and meta character in the same order as in the pattern. Character classes (e.g. [a-d], \n, \r, \t) are considered as one-character node.</li>
 *     <li>Add the end node for the completed state.</li>
 *     <li>Add transition edges. There are two kinds of transition edges: Black <strong>match transition</strong> edge and red <strong>epsilon transition</strong> edge. Match transition is used to move to the next state when a text character is matched with the pattern. Epsilon transition is used to move to different states without matching text characters.</li>
 *     <li>All nodes for matching purpose (e.g. literal ABC or meta character '.' or character class [a-z]): add a <strong>matching edge</strong> to the next node.
 *         <p class="svg">
 *         {@code
 *         <svg width="500" height="50" ><defs id="defs4"><marker refX="0" refY="0" orient="auto" id="Arrow2Mend" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="scale(-0.6,-0.6)" id="path3899" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round"/></marker></defs><path d="m 113.375,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2993" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 47.1875,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3003" style="fill:none;stroke:#000000"/><text x="25.151207" y="28.126936" id="text3021" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="25.151207" y="28.126936" id="tspan3023">A</tspan></text><text x="83.385437" y="28.126936" id="text3025" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="83.385437" y="28.126936" id="tspan3027">...</tspan></text><path d="m 47.32409,25.9879 27.85789,0" id="path4869" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="48.605377" y="23.184187" id="text5180" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="48.605377" y="23.184187" id="tspan5182">match</tspan></text><path d="m 265.93182,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3059" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 199.74432,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3061" style="fill:none;stroke:#000000"/><text x="177.70802" y="28.126936" id="text3063" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="177.70802" y="28.126936" id="tspan3065">.</tspan></text><text x="235.94226" y="28.126936" id="text3067" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="235.94226" y="28.126936" id="tspan3069">...</tspan></text><path d="m 199.88091,25.9879 27.85789,0" id="path3071" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="201.1622" y="23.184187" id="text3073" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="201.1622" y="23.184187" id="tspan3075">match</tspan></text><path d="m 440.22159,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3079" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 374.03409,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3081" style="fill:none;stroke:#000000"/><text x="337.50916" y="28.126936" id="text3083" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="337.50916" y="28.126936" id="tspan3085">[a-z]</tspan></text><text x="410.23203" y="28.126936" id="text3087" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="410.23203" y="28.126936" id="tspan3089">...</tspan></text><path d="m 374.17068,25.9879 27.85789,0" id="path3091" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="375.45197" y="23.184187" id="text3093" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="375.45197" y="23.184187" id="tspan3095">match</tspan></text></svg>
 *         }
 *         </p></li>
 *     <li>For grouping-character nodes (i.e. parenthesis): add an <strong>epsilon edge</strong> to the next node.
 *         <p class="svg">
 *         {@code
 *         <svg width="280" height="50" ><defs id="defs4"><marker refX="0" refY="0" orient="auto" id="Arrow2Mend" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="scale(-0.6,-0.6)" id="path3899" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round"/></marker></defs><path d="m 113.375,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2993" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 47.1875,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3003" style="fill:none;stroke:#ff0000"/><text x="25.151207" y="28.126936" id="text3021" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="25.151207" y="28.126936" id="tspan3023">(</tspan></text><text x="83.385437" y="28.126936" id="text3025" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="83.385437" y="28.126936" id="tspan3027">...</tspan></text><path d="m 47.32409,25.9879 27.85789,0" id="path4869" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 265.93182,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3059" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 199.74432,25.99998 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3061" style="fill:none;stroke:#ff0000"/><text x="177.70802" y="28.126936" id="text3063" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="177.70802" y="28.126936" id="tspan3065">)</tspan></text><text x="235.94226" y="28.126936" id="text3067" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="235.94226" y="28.126936" id="tspan3069">...</tspan></text><path d="m 199.88091,25.9879 27.85789,0" id="path3071" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/></svg>
 *         }
 *         </p></li>
 *     <li>For each or edge (i.e. | ) in a group: add 2 <strong>epsilon edges</strong>: from opening parenthesis ( to the node after | and from | to the closing parenthesis.
 *         <p class="svg">
 *         {@code
 *         <svg width="500" height="100" ><defs id="defs4"><marker refX="0" refY="0" orient="auto" id="Arrow2Mend" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="scale(-0.6,-0.6)" id="path3899" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round"/></marker></defs><path d="m 47.1875,47.87498 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3003" style="fill:none;stroke:#ff0000"/><text x="25.151207" y="50.001938" id="text3021" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="25.151207" y="50.001938" id="tspan3023">(</tspan></text><path d="m 486.53409,47.87498 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3061" style="fill:none;stroke:#ff0000"/><text x="464.4978" y="50.001938" id="text3063" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="464.4978" y="50.001938" id="tspan3065">)</tspan></text><path d="m 163.52272,47.87498 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3644" style="fill:none;stroke:#ff0000"/><path d="m 221.47726,47.87498 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3646" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:6, 1;stroke-dashoffset:0"/><text x="141.41628" y="50.7285" id="text3648" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="141.41628" y="50.7285" id="tspan3650">|</tspan></text><path d="m 322.04545,47.87498 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3652" style="fill:none;stroke:#ff0000"/><path d="m 379.99999,47.87498 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3654" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:6, 1;stroke-dashoffset:0"/><text x="299.939" y="50.7285" id="text3656" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="299.939" y="50.7285" id="tspan3658">|</tspan></text><path d="m 42.613636,60.369319 c 45.59659,23.4375 98.863634,22.585227 147.869314,1.704545" id="path3660" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 40.482954,62.500001 C 124.00568,103.40909 261.22159,103.40909 349.85795,62.926137" id="path3662" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 157.67045,34.375001 C 253.97727,0.71022913 377.98295,1.5625014 456.39204,32.670456" id="path3664" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 315.76704,33.096592 c 50.71022,-15.767045 93.75,-14.488636 137.21591,2.130682" id="path3666" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><text x="193.03976" y="51.551136" id="text4624" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="193.03976" y="51.551136" id="tspan4626">...</tspan></text><text x="351.5625" y="51.551136" id="text4628" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="351.5625" y="51.551136" id="tspan4630">...</tspan></text><text x="241.19318" y="51.551136" id="text4632" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="241.19318" y="51.551136" id="tspan4634">...</tspan></text><text x="403.97726" y="51.551136" id="text4636" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="403.97726" y="51.551136" id="tspan4638">...</tspan></text><text x="75.426132" y="51.551136" id="text4640" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="75.426132" y="51.551136" id="tspan4642">...</tspan></text></svg>
 *         }
 *         </p></li>
 *     <li>For * node: add 3 <strong>epsilon edges</strong>: skip, repeat, forward.
 *         <p class="svg">
 *         {@code
 *         <svg width="500" height="75" ><defs id="defs4"><marker refX="0" refY="0" orient="auto" id="Arrow2Mend" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="scale(-0.6,-0.6)" id="path3899" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round"/></marker></defs><path d="m 107.375,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2993" style="fill:none;stroke:#ff0000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0"/><path d="m 41.1875,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3003" style="fill:none;stroke:#000000"/><text x="19.151207" y="39.126953" id="text3021" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="19.151207" y="39.126953" id="tspan3023">A</tspan></text><text x="85.482025" y="39.126953" id="text3025" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="85.482025" y="39.126953" id="tspan3027">*</tspan></text><path d="M 76.244317,50.7727 C 63.03409,57.5909 47.267045,57.1648 37.465908,48.642" id="path5168" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 36.613636,23.9261 C 50.249999,14.5511 65.164772,13.6989 76.670453,21.7955" id="path5170" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 181.38637,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6050" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 107.37524,36.9879 35.52834,0" id="path6052" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="152.94887" y="41.82373" id="text6054" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="152.94887" y="41.82373" id="tspan6056">...</tspan></text><text x="50.25" y="13.69873" id="text6058" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="50.25" y="13.69873" id="tspan6060">skip</tspan></text><text x="44.710228" y="63.556641" id="text6062" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="44.710228" y="63.556641" id="tspan6064">repeat</tspan></text><text x="109.48296" y="32.875" id="text6066" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="109.48296" y="32.875" id="tspan6068">forward</tspan></text><path d="m 418.0284,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6070" style="fill:none;stroke:#ff0000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0"/><path d="m 264.90909,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6072" style="fill:none;stroke:#ff0000"/><text x="241.16823" y="39.126953" id="text6074" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="241.16823" y="39.126953" id="tspan6076">(</tspan></text><text x="396.13541" y="39.126953" id="text6078" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="396.13541" y="39.126953" id="tspan6080">*</tspan></text><path d="M 386.89772,50.7727 C 339.17045,66.9659 304.66667,68.058667 259.31817,49.418533" id="path6082" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 261.90909,25.0739 C 305.57386,8.3996666 354.93749,6.4545 387.32385,21.7955" id="path6084" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 492.03977,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6086" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 418.02864,36.9879 35.52834,0" id="path6088" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="463.60226" y="41.82373" id="text6090" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="463.60226" y="41.82373" id="tspan6092">...</tspan></text><text x="326.38632" y="8.5854492" id="text6094" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="326.38632" y="8.5854492" id="tspan6096">skip</tspan></text><text x="318.28973" y="72.07959" id="text6098" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="318.28973" y="72.07959" id="tspan6100">repeat</tspan></text><text x="420.13635" y="32.875" id="text6102" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="420.13635" y="32.875" id="tspan6104">forward</tspan></text><path d="m 359.84091,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6106" style="fill:none;stroke:#ff0000"/><text x="338.10004" y="39.126953" id="text6108" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="338.10004" y="39.126953" id="tspan6110">)</tspan></text><text x="288.2822" y="41.82373" id="text6112" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="288.2822" y="41.82373" id="tspan6114">...</tspan></text></svg>
 *         }
 *         </p></li>
 *     <li>For + node: add 2 <strong>epsilon edges</strong>: repeat, forward.
 *         <p class="svg">
 *         {@code
 *         <svg width="500" height="75" ><defs id="defs4"><marker refX="0" refY="0" orient="auto" id="Arrow2Mend" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="scale(-0.6,-0.6)" id="path3899" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round"/></marker></defs><path d="m 107.375,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2993" style="fill:none;stroke:#ff0000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0"/><path d="m 41.1875,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3003" style="fill:none;stroke:#000000"/><text x="19.151207" y="39.126953" id="text3021" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="19.151207" y="39.126953" id="tspan3023">A</tspan></text><text x="85.482025" y="39.126953" id="text3025" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="85.482025" y="39.126953" id="tspan3027">+</tspan></text><path d="M 76.244317,50.7727 C 63.03409,57.5909 47.267045,57.1648 37.465908,48.642" id="path5168" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 181.38637,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6050" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 107.37524,36.9879 35.52834,0" id="path6052" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="152.94887" y="41.82373" id="text6054" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="152.94887" y="41.82373" id="tspan6056">...</tspan></text><text x="44.710228" y="63.556641" id="text6062" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="44.710228" y="63.556641" id="tspan6064">repeat</tspan></text><text x="109.48296" y="32.875" id="text6066" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="109.48296" y="32.875" id="tspan6068">forward</tspan></text><path d="m 418.0284,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6070" style="fill:none;stroke:#ff0000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0"/><path d="m 264.90909,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6072" style="fill:none;stroke:#ff0000"/><text x="241.16823" y="39.126953" id="text6074" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="241.16823" y="39.126953" id="tspan6076">(</tspan></text><text x="396.13541" y="39.126953" id="text6078" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="396.13541" y="39.126953" id="tspan6080">+</tspan></text><path d="M 386.89772,50.7727 C 339.17045,66.9659 304.66667,68.058667 259.31817,49.418533" id="path6082" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 492.03977,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6086" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 418.02864,36.9879 35.52834,0" id="path6088" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="463.60226" y="41.82373" id="text6090" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="463.60226" y="41.82373" id="tspan6092">...</tspan></text><text x="318.28973" y="72.07959" id="text6098" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="318.28973" y="72.07959" id="tspan6100">repeat</tspan></text><text x="420.13635" y="32.875" id="text6102" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="420.13635" y="32.875" id="tspan6104">forward</tspan></text><path d="m 359.84091,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6106" style="fill:none;stroke:#ff0000"/><text x="338.10004" y="39.126953" id="text6108" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="338.10004" y="39.126953" id="tspan6110">)</tspan></text><text x="288.2822" y="41.82373" id="text6112" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="288.2822" y="41.82373" id="tspan6114">...</tspan></text></svg>
 *         }
 *         </p></li>
 *     <li>For ? node: add 2 <strong>epsilon edges</strong>: skip, forward.
 *         <p class="svg">
 *         {@code
 *         <svg width="500" height="75" ><defs id="defs4"><marker refX="0" refY="0" orient="auto" id="Arrow2Mend" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="scale(-0.6,-0.6)" id="path3899" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round"/></marker></defs><path d="m 107.375,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2993" style="fill:none;stroke:#ff0000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0"/><path d="m 41.1875,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3003" style="fill:none;stroke:#000000"/><text x="19.151207" y="39.126953" id="text3021" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="19.151207" y="39.126953" id="tspan3023">A</tspan></text><text x="85.482025" y="39.126953" id="text3025" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="85.482025" y="39.126953" id="tspan3027">?</tspan></text><path d="M 36.613636,23.9261 C 50.249999,14.5511 65.164772,13.6989 76.670453,21.7955" id="path5170" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 181.38637,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6050" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 107.37524,36.9879 35.52834,0" id="path6052" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="152.94887" y="41.82373" id="text6054" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="152.94887" y="41.82373" id="tspan6056">...</tspan></text><text x="50.25" y="13.69873" id="text6058" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="50.25" y="13.69873" id="tspan6060">skip</tspan></text><text x="109.48296" y="32.875" id="text6066" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="109.48296" y="32.875" id="tspan6068">forward</tspan></text><path d="m 418.0284,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6070" style="fill:none;stroke:#ff0000;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;stroke-dashoffset:0"/><path d="m 264.90909,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6072" style="fill:none;stroke:#ff0000"/><text x="241.16823" y="39.126953" id="text6074" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="241.16823" y="39.126953" id="tspan6076">(</tspan></text><text x="396.13541" y="39.126953" id="text6078" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="396.13541" y="39.126953" id="tspan6080">?</tspan></text><path d="M 261.90909,25.0739 C 305.57386,8.3996666 354.93749,6.4545 387.32385,21.7955" id="path6084" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 492.03977,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6086" style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:4, 1;stroke-dashoffset:0"/><path d="m 418.02864,36.9879 35.52834,0" id="path6088" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="463.60226" y="41.82373" id="text6090" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="463.60226" y="41.82373" id="tspan6092">...</tspan></text><text x="326.38632" y="8.5854492" id="text6094" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="326.38632" y="8.5854492" id="tspan6096">skip</tspan></text><text x="420.13635" y="32.875" id="text6102" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="420.13635" y="32.875" id="tspan6104">forward</tspan></text><path d="m 359.84091,37 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path6106" style="fill:none;stroke:#ff0000"/><text x="338.10004" y="39.126953" id="text6108" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="338.10004" y="39.126953" id="tspan6110">)</tspan></text><text x="288.2822" y="41.82373" id="text6112" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="288.2822" y="41.82373" id="tspan6114">...</tspan></text></svg>
 *         }
 *         </p></li>
 * </ul>
 *
 *
 *
 * <p>Example NFA: pattern {@code (A|B|C(X|Y)*).+[a-z]?}</p>
 *
 * <p class="svg">
 * {@code
 * <svg width="1180" height="150" ><defs id="defs4"><marker refX="0" refY="0" orient="auto" id="Arrow2Mend" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="scale(-0.6,-0.6)" id="path3899" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round"/></marker></defs><path d="m 47,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2989" style="fill:none;stroke:#ff0000;stroke-opacity:1"/><path d="m 245.5625,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="use2991" style="fill:none;stroke:#000000;stroke-opacity:1"/><path d="m 179.375,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2993" style="fill:none;stroke:#ff0000"/><path d="m 510.3125,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2995" style="fill:none;stroke:#000000"/><path d="m 311.75,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2997" style="fill:none;stroke:#ff0000"/><path d="m 377.9375,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path2999" style="fill:none;stroke:#000000"/><path d="m 444.125,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3001" style="fill:none;stroke:#ff0000"/><path d="m 113.1875,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3003" style="fill:none;stroke:#000000"/><path d="m 644.79268,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3005" style="fill:none;stroke:#000000"/><path d="m 710.98018,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3007" style="fill:none;stroke:#ff0000"/><text x="24" y="82.126953" id="text3017" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="24" y="82.126953" id="tspan3019">(</tspan></text><text x="91.151207" y="82.126953" id="text3021" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="91.151207" y="82.126953" id="tspan3023">A</tspan></text><text x="157.38544" y="82.126953" id="text3025" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="157.38544" y="82.126953" id="tspan3027">|</tspan></text><text x="223.70755" y="82.126953" id="text3029" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="223.70755" y="82.126953" id="tspan3031">B</tspan></text><text x="289.85974" y="82.126953" id="text3033" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="289.85974" y="82.126953" id="tspan3035">|</tspan></text><text x="356.1174" y="82.126953" id="text3037" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="356.1174" y="82.126953" id="tspan3039">C</tspan></text><text x="421.42291" y="82.126953" id="text3041" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="421.42291" y="82.126953" id="tspan3043">(</tspan></text><text x="488.55948" y="82.126953" id="text3045" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="488.55948" y="82.126953" id="tspan3047">X</tspan></text><text x="623.09515" y="82.126953" id="text3049" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="623.09515" y="82.126953" id="tspan3051">Y</tspan></text><text x="690.17902" y="82.126953" id="text3053" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="690.17902" y="82.126953" id="tspan3055">)</tspan></text><text x="755.5929" y="82.126953" id="text3057" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="755.5929" y="82.126953" id="tspan3059">*</tspan></text><text x="822.65326" y="82.126953" id="text3061" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="822.65326" y="82.126953" id="tspan3063">)</tspan></text><text x="888.04083" y="82.126953" id="text3065" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="888.04083" y="82.126953" id="tspan3067">.</tspan></text><text x="954.29266" y="82.126953" id="text3069" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="954.29266" y="82.126953" id="tspan3071">+</tspan></text><text x="1005.4265" y="82.126953" id="text3073" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="1005.4265" y="82.126953" id="tspan3075">[a-z]</tspan></text><text x="1085.8787" y="82.126953" id="text3077" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="1085.8787" y="82.126953" id="tspan3079">?</tspan></text><path d="m 777.16768,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3081" style="fill:none;stroke:#ff0000"/><path d="m 843.35518,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3083" style="fill:none;stroke:#ff0000"/><path d="m 909.54268,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3085" style="fill:none;stroke:#000000"/><path d="m 975.73018,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3087" style="fill:none;stroke:#ff0000"/><path d="m 1041.9177,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3089" style="fill:none;stroke:#000000"/><path d="m 1108.1052,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3091" style="fill:none;stroke:#ff0000"/><path d="m 1174.2927,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3093" style="fill:none;stroke:#000000"/><path d="m 46.606008,79.98787 27.857886,0" id="path3099" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 113.32409,79.98787 27.85789,0" id="path4869" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 644.03434,79.98787 27.85788,0" id="path4871" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 245.93934,79.98787 27.85788,0" id="path4873" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 377.606,79.98787 27.85789,0" id="path4875" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 509.63232,79.98787 27.85789,0" id="path4877" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 444.27268,79.98787 27.85788,0" id="path4879" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 1108.5709,79.88261 27.8579,0" id="path4881" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 843.23759,79.85629 27.85788,0" id="path4883" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 777.58846,80.18086 27.85789,0" id="path4885" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 711.23759,80.86507 27.85788,0" id="path4887" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="M 42.631579,92.36842 C 85.29825,125.03512 167.66667,126.00002 213.66667,94" id="path3173" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 38.666667,95.66667 C 132.55263,151.44742 253,151.66672 347.33333,94.33334" id="path3961" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 575.5122,80 a 18.5,18.5 0 0 1 -37,0 18.5,18.5 0 1 1 37,0 z" id="path3965" style="fill:none;stroke:#ff0000"/><path d="m 440.26316,91.6579 c 46.05263,28.94732 130.92105,23.68422 170.39474,0.6579" id="path3990" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 572.5,67.31579 C 619.21053,41 656.71053,52.18421 679.73684,64.68421" id="path3992" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 175.78947,67.31579 C 381.05263,2.84211 618.21052,0.52632 811.63158,65.00001" id="path3994" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 306.71053,66.6579 C 460.65789,19.28948 660.65789,19.94737 808.68421,67.97369" id="path3996" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 442.23684,70.60527 c 99.34211,-38.81579 215.78947,-36.8421 300,-1.31579" id="path3998" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 744.86842,92.97369 c -73.68421,48.02633 -227.63158,47.36843 -305.26316,2.63157" id="path4000" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="M 943.55263,91.6579 C 924.47368,98.23682 917.23684,96.26316 906.71053,91" id="path4002" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 1033.5421,64.16842 c 24.3421,-9.86842 31.7211,-6.72105 46.1947,-0.8" id="path4004" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Mend)"/><path d="m 909.88671,79.88261 27.85789,0" id="path4006" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 975.67618,79.88261 27.85792,0" id="path4008" style="fill:none;stroke:#ff0000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><path d="m 1042.1235,80.54051 27.8579,0" id="path4010" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Mend)"/><text x="1046.8422" y="54.8158" id="text5140" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="1046.8422" y="54.8158" id="tspan5142">skip</tspan></text><text x="908.6842" y="104.8158" id="text5144" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="908.6842" y="104.8158" id="tspan5146">repeat</tspan></text><text x="575.52075" y="451.12683" transform="matrix(0.87569382,-0.48286679,0.48286679,0.87569382,0,0)" id="text5148" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="575.52075" y="451.12683" id="tspan5150">repeat</tspan></text><text x="401.49301" y="198.19823" transform="matrix(0.95191241,-0.30637032,0.30637032,0.95191241,0,0)" id="text5152" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="401.49301" y="198.19823" id="tspan5154">skip</tspan></text><text x="1043.5527" y="77.184204" id="text5156" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="1043.5527" y="77.184204" id="tspan5158">match</tspan></text><text x="911.31592" y="77.184204" id="text5160" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="911.31592" y="77.184204" id="tspan5162">match</tspan></text><text x="644.86853" y="77.184204" id="text5164" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="644.86853" y="77.184204" id="tspan5166">match</tspan></text><text x="510.65802" y="77.184204" id="text5168" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="510.65802" y="77.184204" id="tspan5170">match</tspan></text><text x="378.42117" y="77.184204" id="text5172" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="378.42117" y="77.184204" id="tspan5174">match</tspan></text><text x="246.18433" y="77.184204" id="text5176" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="246.18433" y="77.184204" id="tspan5178">match</tspan></text><text x="114.60538" y="77.184204" id="text5180" xml:space="preserve" style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Sans;-inkscape-font-specification:Sans"><tspan x="114.60538" y="77.184204" id="tspan5182">match</tspan></text><path d="m 1149.8,84.6 c 2.2,2.2 3.2,3.4 4.4,5.8 0.8,-9 2.6,-13.8 7.2,-20.8" id="path6626" style="fill:none;stroke:#ff0000;stroke-width:2.29999995;stroke-linecap:round;stroke-linejoin:round;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none"/><text x="553.40576" y="82.126953" id="text7091" xml:space="preserve" style="font-size:12px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold"><tspan x="553.40576" y="82.126953" id="tspan7093">|</tspan></text></svg>
 * }
 * </p>
 *
 *
 *
 *
 * @author Trung Phan
 *
 */
public class RegExp {

    private static final Node END_NODE = new Node('\0', '\0');

    private static final Set<Character> META_CHARS = new HashSet<>(Arrays.asList('(', ')', '|', '+', '*', '?', '.'));
    private static final Set<Character> UNSUPPORTED_META_CHARS = new HashSet<>(Arrays.asList('{', '}', '^', '$'));

    private final Node root;

    public RegExp(String pattern) {

        List<Node> nodes = buildStates(pattern);

        this.root = buildStateTransitions(nodes);
    }

    private static List<Node> buildStates(String pattern) {
        List<Node> nodes = new ArrayList<>();

        int i = 0;
        while (i < pattern.length()) {
            char ch = pattern.charAt(i++);
            if (UNSUPPORTED_META_CHARS.contains(ch)) {
                throw new IllegalArgumentException("Unsupported: " + ch);
            }
            else if (META_CHARS.contains(ch)) {
                nodes.add(Node.newMetaNode(ch));
            }
            else if (ch == '[') {
                ch = pattern.charAt(i++);
                boolean negated = false;
                Set<Character> chars = new HashSet<>();
                if (ch == '^') {
                    negated = true;
                    ch = pattern.charAt(i++);
                }
                if (ch == ']') {
                    chars.add(']');
                    ch = pattern.charAt(i++);
                }
                else if (ch == '-') {
                    chars.add('-');
                    ch = pattern.charAt(i++);
                }

                for  (; ch != ']'; ch = pattern.charAt(i++)) {
                    if (ch == '-' && pattern.charAt(i) != ']') {
                        for (char c = pattern.charAt(i-2); c <= pattern.charAt(i); c++) {
                            chars.add(c);
                        }
                    }
                    else {
                        chars.add(ch);
                    }
                }
                nodes.add(new Node(negated, chars));
            }
            else if (ch == '\\') {
                ch = pattern.charAt(i++);
                nodes.add(Node.newNode(ch == 'n' ? '\n' : ch == 'r' ? '\r' : ch == 't' ? '\t' : ch));
            }
            else {
                nodes.add(Node.newNode(ch));
            }
        }

        nodes.add(END_NODE);
        return nodes;
    }

    private static Node buildStateTransitions(List<Node> nodes) {
        Stack<Integer> metaOperators = new Stack<>(); // to handle )

        for (int i = 0; i < nodes.size() - 1; i++) {
            Node node = nodes.get(i);
            Node next = nodes.get(i+1);

            Node prevNode = null; // to handle * and +

            if (node.matchMeta('(')) {
                nodes.get(i).epsilonEdges.add(next);
                metaOperators.push(i);
            }
            else if (node.matchMeta('|')) {
                metaOperators.push(i);
            }
            else if (node.matchMeta(')')) {
                node.epsilonEdges.add(next);

                for (Integer prevOp : metaOperators) {
                    if (nodes.get(prevOp).matchMeta('(')) {
                        prevNode = nodes.get(prevOp);
                        break;
                    }
                }
                if (prevNode == null) {
                    throw new IllegalArgumentException();
                }

                int or;
                while ( nodes.get(or = metaOperators.pop()).matchMeta('|')  ) {
                    prevNode.epsilonEdges.add(nodes.get(or + 1));
                    nodes.get(or).epsilonEdges.add(node);
                }
            }
            else if (node.matchMeta('*') || node.matchMeta('+') || node.matchMeta('?')) {
                node.epsilonEdges.add(next);
            }
            else {
                // char node or .
                node.matchEdge = next;
                prevNode = node;
            }

            if ( next.matchMeta('*') || next.matchMeta('+') || next.matchMeta('?') ) { // look ahead
                if (prevNode == null) {
                    throw new IllegalArgumentException(next.metaChar + " is misplaced");
                }

                if (next.matchMeta('*') || next.matchMeta('+')) {
                    next.epsilonEdges.add(prevNode); // repeat
                }

                if (next.matchMeta('*') || next.matchMeta('?')) {
                    prevNode.epsilonEdges.add(next); // skip
                }
            }
        }

        return nodes.get(0);
    }

    public boolean match(String text) {

        Set<Node> activeStates = getPossibleNextStates(Arrays.asList(root));

        for (int i = 0; i < text.length(); i++) {
            char ch = text.charAt(i);
            Set<Node> nextStates = new HashSet<>();
            for (Node state : activeStates) {
                if (state.matchChar(ch)) {
                    nextStates.add(state.matchEdge);
                }
            }
            activeStates = getPossibleNextStates(nextStates);

            if (activeStates.size() == 0) {
                return false;
            }
        }

        return activeStates.contains(END_NODE);
    }

    private static Set<Node> getPossibleNextStates(Collection<Node> activeStates) {
        Set<Node> possibleNextStates = new HashSet<>(activeStates);
        Queue<Node> queue = new LinkedList<>(activeStates);

        while (!queue.isEmpty()) { // breadth first search
            Node n = queue.remove();

            for (Node w : n.epsilonEdges) {
                if (!possibleNextStates.contains(w)) {
                    possibleNextStates.add(w);
                    queue.add(w);
                }
            }
        }

        return possibleNextStates;
    }


    public static class Node {

        private final char metaChar;

        private final char ch;

        private final Set<Character> otherChars = new HashSet<>();

        private final boolean negated;

        private Node matchEdge;

        private List<Node> epsilonEdges = new ArrayList<>();

        public Node(char metaChar, char ch) {
            this.metaChar = metaChar;
            this.ch = ch;
            negated = false;
        }

        public Node(boolean negated, Collection<Character> chars) {
            this.metaChar = '\0';
            this.ch = '\0';
            this.negated = negated;
            this.otherChars.addAll(chars);
        }

        public static Node newNode(char ch) {
            return new Node('\0', ch);
        }

        public static Node newMetaNode(char metaChar) {
            return new Node(metaChar, '\0');
        }

        public boolean matchMeta(char ch) {
            return this.metaChar != '\0' && this.metaChar == ch;
        }

        public boolean matchChar(char ch) {
            if (this.metaChar == '.') {
                return true;
            }

            if (this.metaChar != '\0') {
                return false;
            }

            if (otherChars.size() > 0) {
                return negated ? !otherChars.contains(ch) : otherChars.contains(ch);
            }

            return this.ch == ch;
        }

    }

}
